package sjjg.tree;

import java.util.ArrayDeque;
import java.util.Queue;

public class OrigamiQuestion {
    class Node{//内部类
        String value;
        Node left;
        Node right;

        public Node(String value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
   public Node createTree(int N){
        Node root=null;
       for (int i = 0; i < N; i++) {
           if(i==0){//如果是第一次进入
               root=new Node("down",null,null);
               continue;
           }
           ArrayDeque<Node> arrayDeque = new ArrayDeque<>();
           arrayDeque.add(root);
           //层序遍历
           while (!arrayDeque.isEmpty()){
                 //弹出第一个元素
               Node pop = arrayDeque.pop();
               //判断左子树是否为空
               if(pop.left!=null){
                   arrayDeque.add(pop.left);
               }
               //判断右子树是否为空
               if(pop.right!=null){
                   arrayDeque.add(pop.right);
               }
               if(pop.left==null && pop.right==null){
                  pop.left=new Node("down",null,null);
                  pop.right=new Node("up",null,null);
               }
           }
       }
       return root;
   }
   public void midPrint(Node tree){
        if(tree==null){
            return;
        }
        if (tree.left!=null){
            midPrint(tree.left);
        }
       System.out.print(tree.value+" ");
        if(tree.right!=null){
            midPrint(tree.right);
        }
   }

    public static void main(String[] args) {
        OrigamiQuestion origamiQuestion = new OrigamiQuestion();
        Node tree = origamiQuestion.createTree(7);
        origamiQuestion.midPrint(tree);
    }
}
